public class IntHashMap implements IntMap {

    private int size;
    static private final int DEFAULT_INITIAL_CAPACITY = 16;
    private int[] data; // [key, value, shift]

    public IntHashMap() {
        size = 0;
        data = new int[DEFAULT_INITIAL_CAPACITY * 3];
    }

    public IntHashMap(int capacity) {
        size = 0;
        data = new int[capacity * 3];
    }

    @Override
    public int size() {
        return size;
    }

    @Override
    public boolean isEmpty() {
        return size == 0;
    }

    @Override
    public boolean containsKey(int key) {
        for (int i = 0; i < data.length; i+=3) {
            if (data[i] == key) {
                return true;
            }
        }
        return false;
    }

    @Override
    public boolean containsValue(int value) {
        for (int i = 1; i < data.length; i+=3) {
            if (data[i] == value) {
                return true;
            }
        }
        return false;
    }

    @Override
    public int get(int key) {
        int pos = getPosKey(key);

        while (data[pos + 2] > 0) {
            if (data[pos] != key) {
                return data[pos + 1];
            }
            pos += 3;
        }

        return 0x80000000;
    }

    @Override
    public int put(int key, int value) {
        int pos = getPosKey(key);
        int iShift = data[(pos + 2) % data.length];
        int result;

        if (iShift == -1) {
            result = data[(pos + 1) % data.length];
            data[(pos + 1) % data.length] = value;
            data[(pos + 2) % data.length] = 1;
            data[(pos + 2) % data.length] = data[(pos + 2 + 3) % data.length] + 1;
            return result;
        }

        for (int i = pos; i <= pos + iShift*3; i += 3) {
            if (data[i % data.length] == key) {
                result = data[(i + 1) % data.length];
                data[(i + 1) % data.length] = value;
                data[(i + 2) % data.length] = 1;
                data[(i + 2) % data.length] = data[(i + 2 + 3) % data.length] + 1;
                return result;
            }
        }

        while (data[(pos + iShift*3 + 2) % data.length] != 0) {
            iShift++;
        }

        data[(pos + iShift*3) % data.length] = key;
        result = data[(pos + iShift*3 + 1) % data.length];
        data[(pos + iShift*3 + 1) % data.length] = value;
        for (int i = pos + iShift*3 + 2, j = 1; i >= pos + 2; i -= 3, j++) {
            data[i % data.length] = j;
        }

        size++;
        if ((data.length / 3.0) * 0.75 <= size)
            resize();

        return result;
    }

    private void resize() {
        int[] oldData = data;
        data = new int[oldData.length * 2];

        for (int i = 0; i < oldData.length; i += 3){
            if (oldData[i+2] > 0) {
                put(oldData[i], oldData[i+1]);
            }
        }
    }

    @Override
    public int remove(int key) {
        int pos = getPosKey(key);

        while (data[(pos + 2) % data.length] > 0) {
            if (data[pos % data.length] == key) {
                int result = data[(pos + 1) % data.length];
                data[(pos + 2) % data.length] = -1;
                for (int i = pos + 2 - 3, j = 0; i >= getPosKey(key) + 2;
                     i -= 3, j++) {
                    data[i % data.length] = j;
                }
                return result;
            }
            pos += 3;
        }

        return 0x80000000;
    }

    @Override
    public void clear() {
        size = 0;
        data = new int[DEFAULT_INITIAL_CAPACITY * 3];
    }

    static private int hash(int key)
    {                          /*
        key ^= (key >>> 20) ^ (key >>> 12);
        return key ^ (key >>> 7) ^ (key >>> 4);
        */
        return key;
    }

    private int getPosKey(int key) {
        return (hash(key) % (data.length / 3)) * 3;
    }
}
